#ifndef PENTOMINOES_H
#define PENTOMINOES_H

using namespace std;

#include <vector>
#include <map>

#define PENTO_SIZE 5
#define PUZZLE_ROWS 11 
#define PUZZLE_COLS 7

typedef char pentomino_map[PENTO_SIZE][PENTO_SIZE];
typedef char puzzle_bitmap[PUZZLE_ROWS][PUZZLE_COLS];
typedef pair<int, int> coord;

// Pentomino shapes
char f_shape[][PENTO_SIZE] = {
	{' ', 'F', 'F', ' ', ' '},
	{'F', 'F', ' ', ' ', ' '},
	{' ', 'F', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char i_shape[][PENTO_SIZE] = {
	{'I', ' ', ' ', ' ', ' '},
	{'I', ' ', ' ', ' ', ' '},
	{'I', ' ', ' ', ' ', ' '},
	{'I', ' ', ' ', ' ', ' '},
	{'I', ' ', ' ', ' ', ' '}
};

char l_shape[][PENTO_SIZE] = {
	{'L', ' ', ' ', ' ', ' '},
	{'L', ' ', ' ', ' ', ' '},
	{'L', ' ', ' ', ' ', ' '},
	{'L', 'L', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char n_shape[][PENTO_SIZE] = {
	{' ', 'N', ' ', ' ', ' '},
	{'N', 'N', ' ', ' ', ' '},
	{'N', ' ', ' ', ' ', ' '},
	{'N', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char p_shape[][PENTO_SIZE] = {
	{'P', 'P', ' ', ' ', ' '},
	{'P', 'P', ' ', ' ', ' '},
	{'P', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char t_shape[][PENTO_SIZE] = {
	{'T', 'T', 'T', ' ', ' '},
	{' ', 'T', ' ', ' ', ' '},
	{' ', 'T', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char u_shape[][PENTO_SIZE] = {
	{'U', ' ', 'U', ' ', ' '},
	{'U', 'U', 'U', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char v_shape[][PENTO_SIZE] = {
	{'V', ' ', ' ', ' ', ' '},
	{'V', ' ', ' ', ' ', ' '},
	{'V', 'V', 'V', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char w_shape[][PENTO_SIZE] = {
	{'W', ' ', ' ', ' ', ' '},
	{'W', 'W', ' ', ' ', ' '},
	{' ', 'W', 'W', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char x_shape[][PENTO_SIZE] = {
	{' ', 'X', ' ', ' ', ' '},
	{'X', 'X', 'X', ' ', ' '},
	{' ', 'X', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char y_shape[][PENTO_SIZE] = {
	{' ', 'Y', ' ', ' ', ' '},
	{'Y', 'Y', ' ', ' ', ' '},
	{' ', 'Y', ' ', ' ', ' '},
	{' ', 'Y', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

char z_shape[][PENTO_SIZE] = {
	{'Z', 'Z', ' ', ' ', ' '},
	{' ', 'Z', ' ', ' ', ' '},
	{' ', 'Z', 'Z', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '},
	{' ', ' ', ' ', ' ', ' '}
};

class pentomino {
	public:
		pentomino(pentomino_map& pb);
		~pentomino();
		char at(int i, int j);
		void set(int i, int j, char val);
		bool identical(pentomino &p);
		pentomino& copy();
		pentomino& translate(int dx, int dy);
		pentomino& reflect();
		pentomino& rotate90();
		pentomino& rotate90_n(int n);
		void orientations(vector<pentomino>& orient);
		void print();
	private:
		pentomino_map bitmap;
		int size;
};


typedef vector< pair<coord, pentomino> > solution;

class puzzle {
	public:
		puzzle(puzzle_bitmap& pb, int r, int c, 
				vector<pentomino>& sh);
		~puzzle();
		bool solve(vector<pentomino>& sh, 
				vector<coord>& filled);
		void print_solution();
	private:
		puzzle_bitmap bitmap;
		int rows;
		int cols;
		vector<pentomino> shapes;
		solution sol;

		bool inside(int i, int j);
		void neighbors(int i, int j, puzzle_bitmap& pb, vector<coord>& n);
		bool done(vector<coord>& filled);
		bool eval(pentomino p, int x, int y, vector<coord>& filled);
		bool fits(pentomino p, int x, int y, vector<coord>& filled);
};

#endif
